package nl.utwente.eemcs.common.analysis;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

import nl.utwente.eemcs.common.helpers.DataEdge;
import nl.utwente.eemcs.common.helpers.DataItem;
import nl.utwente.eemcs.common.helpers.GraphBuilder;
import nl.utwente.eemcs.graph.*;

public class DataDependencyAnalyzer {
	public static void analyze(GraphBuilder graphBuilder) throws AnalysisException {
		createDataDependencies(graphBuilder);
	}

	private static void createDataDependencies(GraphBuilder graphBuilder) throws AnalysisException {
		HashMap<String, DataItem> dataItems = graphBuilder.getDataItems();
		HashMap<Node, DataEdge> dataEdges = new HashMap<Node, DataEdge>();
		
		for (String dataItem : dataItems.keySet()) {
			// Clear the data edges set
			dataEdges.clear();
			
			// Filter the data edges for the current data item
			for (DataEdge edge : graphBuilder.getDataEdges()) {
				if (edge.getDataItem() == dataItems.get(dataItem))
					dataEdges.put(edge.getNode(), edge);
			}
			// Walk through graph and create data edges
			walkGraph(graphBuilder.getGraph().getStartNode(), graphBuilder.getGraph(), graphBuilder.getGraph(), dataEdges, new HashSet<Node>(), new ArrayList<Node>());
		}
	}
	
	private static void walkGraph(Node currentNode, Graph currentGraph, Graph lookupGraph, HashMap<Node, DataEdge> dataEdges, HashSet<Node> possibleWriters, List<Node> visitedNodes)  throws AnalysisException {
		// When the current node has already been visited, return
		if (visitedNodes.contains(currentNode))
			return;
		
		// Add currentNode to visited list
		visitedNodes.add(currentNode);		
		
		// When the current node is present in the data edges map, create data dependencies
		if (dataEdges.containsKey(currentNode)) {
			switch (dataEdges.get(currentNode).getEdgeType()) {
			case Create:
				// After a create, the currentNode is a possible writer
				possibleWriters.add(currentNode);
				// Create data edge
				createDataEdge(lookupGraph, currentNode, currentNode, dataEdges.get(currentNode));
				break;
			case Read:
				// Create data edges from the current writers to the current node
				createDataEdges(lookupGraph, possibleWriters, currentNode, dataEdges.get(currentNode));				
				break;
			case ReadWrite:
			case Write:
				// Create data edges from the current writers to the current node
				createDataEdges(lookupGraph, possibleWriters, currentNode, dataEdges.get(currentNode));
				
				// When the execution of the node is guaranteed, the current node is the only writer for the node
				if (currentNode.isExecutionGuaranteed())
					possibleWriters.clear();
				
				// When a write or read/write is performed, add the current node to writers list				
				possibleWriters.add(currentNode);
				break;
			default:
				// Create data edges from the current writers to the current node
				createDataEdges(lookupGraph, possibleWriters, currentNode, dataEdges.get(currentNode));
				
				// In case of destroy, remove the possible writers
				possibleWriters.clear();
				break;
			}
		}
		
		// Get outgoing edges
		List<Edge> outgoingEdges = currentGraph.getOutgoingEdges(currentNode, EdgeType.Control);
		
		/**
		 * Deal with composite constructs
		 */
		if (currentNode instanceof CompositeNode) {
			if (currentNode instanceof Partition) {
				Graph g = ((Partition)currentNode).getInnerGraph();
				walkGraph(g.getStartNode(), g, lookupGraph, dataEdges, possibleWriters, visitedNodes);
			} else if (currentNode instanceof LoopConstruct) {
				Graph g = ((LoopConstruct)currentNode).getInnerGraph();
				walkGraph(g.getStartNode(), g, lookupGraph, dataEdges, possibleWriters, visitedNodes);
			} else {
				HashSet<Node> newPossibleWriters = new HashSet<Node>();
				BranchedConstruct<?, ?> branched = (BranchedConstruct<?,?>)currentNode;
				boolean newWritersFound = false;
				for (Graph g : branched.getBranches()) {
					HashSet<Node> posWritersBranch = new HashSet<Node>();
					posWritersBranch.addAll(possibleWriters);
					
					// Walk the branch
					walkGraph(g.getStartNode(), g, lookupGraph, dataEdges, posWritersBranch, visitedNodes);
					
					if (!isHashSetTheSame(posWritersBranch, possibleWriters)) {
						// Merge the new possible writers with the current set
						newPossibleWriters.addAll(posWritersBranch);
						newWritersFound = true;
					}
				}
				
				// If new writers are found, copy to the new list
				if (newWritersFound) {
					// Copy new possible writers to current possible writers set
					possibleWriters.clear();
					possibleWriters.addAll(newPossibleWriters);
				}
			}
		}
		
		// Examine outgoing edges
		if (outgoingEdges.size() == 0)
			return;
		else if (outgoingEdges.size() == 1)
			walkGraph(outgoingEdges.get(0).getEnd(), currentGraph, lookupGraph, dataEdges, possibleWriters, visitedNodes);
		else
			throw new AnalysisException("Node found with multiple outgoing edges, which is not allowed for current node type");
	}

	private static void createDataEdges(Graph currentGraph, HashSet<Node> writerSet, Node currentNode, DataEdge dataEdge) {
		if (writerSet.size() == 0)
			createDataEdge(currentGraph, currentNode, currentNode, dataEdge);
		else
			for (Node writer : writerSet)
				createDataEdge(currentGraph, writer, currentNode, dataEdge);
	}
	
	private static void createDataEdge(Graph currentGraph, Node from, Node to, DataEdge dataEdge) {
		Edge newEdge = new Edge(from, to, EdgeType.Data);
		newEdge.addAttribute("dataItem", dataEdge.getDataItem());
		newEdge.addAttribute("relationType", dataEdge.getEdgeType());
		newEdge.setLabel(dataEdge.getDataItem().getName());
		currentGraph.addEdge(newEdge);
	}
	
	/**
	 * Checks if the contents of two hashsets is the same
	 * @param h1 Hashset 1
	 * @param h2 Hashset 2
	 * @return True, if the hashsets have the same contents
	 */
	private static boolean isHashSetTheSame(HashSet<?> h1, HashSet<?> h2) {
		if (h1.size() != h2.size())
			return false;
		
		// Compare contents
		for (Object h : h1)
			if (!h2.contains(h))
				return false;
		
		return true;
	}
}